#include <chrono>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

void print_arr(int *arr, const uint32_t start, uint32_t end) {
  for (size_t j = start; j <= end; j++) {
    std::cout << arr[j] << ", ";
  }
  std::cout << std::endl;
}
void swap_item(const uint32_t index1, const uint32_t index2, int *arr);
void topk_pivot(int *arr, const uint32_t p, const uint32_t q, const int k) {
  int32_t len = q - p + 1;
  if (len <= 1) {
    return;
  } else if (len == 2) {
    if (arr[p] > arr[q]) {
      swap_item(p, q, arr);
    }
    return;
  }
  if (k <= 0) {
    return;
  }
  auto pivot = arr[q];
  size_t scan_index = p, first_larger_index = p;
  /* find first larger than pivot index */
  for (; scan_index < q; ++scan_index) {
    if (arr[scan_index] > pivot) {
      first_larger_index = scan_index;
      break;
    }
  }
  /* sort array base on pivot */
  for (; scan_index < q; ++scan_index) {
    if (arr[scan_index] < pivot) {
      swap_item(scan_index, first_larger_index, arr);
      ++first_larger_index;
    }
  }

  /*swap pivot*/
  swap_item(q, first_larger_index, arr);
  ++first_larger_index;

  /*sort sub array*/
  topk_pivot(arr, first_larger_index, q, k);
  const uint32_t right_len = q - first_larger_index + 1;
  if (right_len < k) {
    uint32_t tmp2 = (first_larger_index > p + 2) ? (first_larger_index - 2) : p;
    topk_pivot(arr, p, tmp2, k - right_len - 1);
  }
}

void topk_pivot(int *arr, const uint32_t len, const int k) {
  topk_pivot(arr, 0, len - 1, k);
}

void swap_item(const uint32_t index1, const uint32_t index2, int *arr) {
  auto tmp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = tmp;
}

void quick_sort(int *arr, const uint32_t p, const uint32_t q) {
  int32_t len = q - p + 1;
  if (len <= 1) {
    return;
  } else if (len == 2) {
    if (arr[p] > arr[q]) {
      swap_item(p, q, arr);
    }
    return;
  }
  auto pivot = arr[q];
  size_t scan_index = p, first_larger_index = p;
  /* find first larger than pivot index */
  for (; scan_index < q; ++scan_index) {
    if (arr[scan_index] > pivot) {
      first_larger_index = scan_index;
      break;
    }
  }
  /* sort array base on pivot */
  for (; scan_index < q; ++scan_index) {
    if (arr[scan_index] < pivot) {
      swap_item(scan_index, first_larger_index, arr);
      ++first_larger_index;
    }
  }

  /*swap pivot*/
  swap_item(q, first_larger_index, arr);
  ++first_larger_index;

  /*sort sub array*/
  uint32_t tmp2 = (first_larger_index > p + 2) ? (first_larger_index - 2) : p;
  quick_sort(arr, p, tmp2);
  quick_sort(arr, first_larger_index, q);
}

void quick_sort(int *arr, const uint32_t len) { quick_sort(arr, 0, len - 1); }

uint32_t get_heap_parent(const uint32_t child_index) {
  return (child_index - 1) / 2;
}

uint32_t get_heap_child(const uint32_t parent_index) {
  return (2*parent_index + 1);
}

void check_child(int *arr, const uint32_t parent_index,
                 const uint32_t max_index) {
  auto child_l = get_heap_child(parent_index);
  if (child_l > max_index) {
    return;
  }
  auto child_r = child_l + 1;
  if (child_r > max_index) {
    child_r = child_l;
  }

  if (arr[parent_index] > arr[child_l]) {
    swap_item(child_l, parent_index, arr);
    check_child(arr, child_l, max_index);
  }

  if (arr[parent_index] > arr[child_r]) {
    swap_item(child_r, parent_index, arr);
    check_child(arr, child_r, max_index);
  }
}

void cast_mini_heap(int *arr, const size_t size) {
  uint32_t max_index = size - 1;
  for (size_t i = max_index; i > 0; --i) {
    auto parent = get_heap_parent(i);
    if(arr[i] < arr[parent]) {
      swap_item(i, parent, arr);
      check_child(arr, i, max_index);
    }
  }
}

void topk_heap(int *arr, const uint32_t len, const int k) {
  cast_mini_heap(arr, k);
  for (size_t i = k; i < len; i++) {
    if(arr[i]>arr[0]) {
      swap_item(i, 0, arr);
      cast_mini_heap(arr, k);
    }
  }
}

void cast_random_array(int *arr, uint32_t len) {
  // 随机生成数组
  for (int i = 0; i < len; i++) {
    arr[i] = rand()%100000;
  }
}

int main() {
#define LEN 20000
  int arr[LEN];
  uint32_t len = sizeof(arr) / sizeof(arr[0]);
  cast_random_array(arr, len);
  // 打印数组
  if (len <= 20) {
    for (int i = 0; i < len; i++) {
      cout << arr[i] << " ";
    }
    std::cout << std::endl;
  }
  int quick_arr[LEN];
  memcpy(quick_arr, arr, sizeof(arr));
  auto start = std::chrono::high_resolution_clock::now();
  quick_sort(quick_arr, len);
  auto end = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double> duration = end - start;
  cout << "quick_sort cost time: " << duration.count() / 1000 << " us"
       << std::endl;
  int topk_arr[LEN];
  memcpy(topk_arr, arr, sizeof(arr));
  start = std::chrono::high_resolution_clock::now();
  topk_pivot(topk_arr, len, 10);
  end = std::chrono::high_resolution_clock::now();
  duration = end - start;
  cout << "cost time: " << duration.count() / 1000 << " us" << std::endl;
  std::cout << "Result: ";
  for (int i = len - 10; i < len; i++) {
    cout << topk_arr[i] << " vs " << quick_arr[i] << ", \n";
  }
  std::cout << std::endl;

  int topk_arr1[LEN];
  memcpy(topk_arr1, arr, sizeof(arr));
  start = std::chrono::high_resolution_clock::now();
  topk_heap(topk_arr1, len, 10);
  end = std::chrono::high_resolution_clock::now();
  duration = end - start;
  cout << "cost time: " << duration.count() / 1000 << " us" << std::endl;
  std::cout << "Result: ";
  print_arr(topk_arr1, 0, 9);

  for (size_t i = 0; i < len; i++) {
    if (arr[i] == 99950) {
      std::cout << "!!!!!!!!!!!\n";
      break;
    }
  }

  quick_sort(topk_arr1, 10);
  print_arr(topk_arr1, 0, 9);
  return 0;
}